home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / C / ESPRESSO.ZIP / POP.C < prev    next >
Encoding:
C/C++ Source or Header  |  1987-03-14  |  3.0 KB  |  99 lines
  1. #include "espresso.h"
  2.  
  3. bool pop_expand(Fin, D)
  4. INOUT pcover *Fin;
  5. IN pcover D;
  6. {
  7.     bool change, expanded = FALSE, removed = FALSE;
  8.     pcover F = *Fin;
  9.     pcube *FD;
  10.     register pcube p, p1, last, newp;
  11.     register int i, n = cube.num_binary_vars - 1;
  12.     newp = new_cube();
  13.  
  14.     /* Use cube-size heuristic to order the cubes for expansion */
  15.     sf_active(F = size_sort(F));
  16.  
  17.     /* Attempt to expand each nonprime and noncovered cube */
  18.     FD = cube2list(F, D);
  19.     foreach_set(F, last, p)
  20.         if (TESTP(p, ACTIVE) && ! TESTP(p, PRIME)) {
  21.             change = FALSE;
  22.             set_copy(newp, p);
  23.             for(i = 0; i <= cube.last_part[n]; i++)
  24.                 if (! is_in_set(newp, i)) {
  25.                     set_insert(newp, i);
  26.                     if (cube_is_covered(FD, newp))
  27.                         change = TRUE;
  28.                     else
  29.                         set_remove(newp, i);
  30.                 }
  31.             if (change) {
  32.                 if (debug & EXPAND)
  33.                     printf("EXPAND: %s to %s\n", pc1(p), pc2(newp));
  34.                 set_copy(p, newp);
  35.                 for(p1 = p + F->wsize; p1 < last; p1 += F->wsize)
  36.                     if (setp_implies(p1, p)) {
  37.                         if (debug & EXPAND)
  38.                             printf("deleted %s\n", pc1(p1));
  39.                         removed = TRUE, F->active_count--, RESET(p1, ACTIVE);
  40.                     }
  41.                 expanded = TRUE;
  42.             }
  43.             SET(p, PRIME);
  44.         }
  45.     free_cubelist(FD);
  46.  
  47.     /* Delete any cubes of F which became covered during the expansion */
  48.     if (removed)
  49.         F = sf_inactive(F);
  50.  
  51.     free_cube(newp);
  52.     *Fin = F;
  53.     return expanded;
  54. }
  55.  
  56. bool pop_reduce(Fin, D)
  57. INOUT pcover *Fin;
  58. IN pcover D;
  59. {
  60.     bool change, reduced = FALSE, removed = FALSE;
  61.     pcover F = *Fin;
  62.     pcube *FD;
  63.     register int i, n = cube.num_vars - 1;
  64.     register pcube p, last, newp = cube.temp[7], temp = cube.temp[8];
  65.  
  66.     /* Use cube-size heuristic to order the cubes for reduction */
  67.     sf_active(F = size_sort(F));
  68.  
  69.     /* Attempt to reduce each cube of F */
  70.     FD = cube2list(F, D);
  71.     foreach_set(F, last, p) {
  72.         change = FALSE;
  73.         set_copy(newp, p);
  74.         for(i = cube.first_part[n]; i <= cube.last_part[n]; i++)
  75.             if (is_in_set(p, i)) {
  76.                 set_remove(p, i);
  77.                 if (cube_is_covered(FD, newp))
  78.                     change = TRUE;
  79.                 else
  80.                     set_insert(p, i);
  81.             }
  82.         if (change) {
  83.             if (debug & REDUCE)
  84.                 printf("POP_REDUCE: %s reduced to %s\n", pc1(newp), pc2(p));
  85.             reduced = TRUE;
  86.             RESET(p, PRIME);
  87.             if (setp_empty(set_and(temp, p, cube.var_mask[n])))
  88.                 removed = TRUE, F->active_count--, RESET(p, ACTIVE);
  89.         }
  90.     }
  91.     free_cubelist(FD);
  92.  
  93.     /* Delete any cubes of F which disappeared during the reduction */
  94.     if (removed)
  95.         F = sf_inactive(F);
  96.     *Fin = F;
  97.     return reduced;
  98. }
  99.